#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// 表示皇后在棋盘上的位置
struct QueenPos {
    int row, col;
};

// 检查当前位置是否可以放置皇后
bool isSafe(QueenPos pos, vector<QueenPos>& queens) {
    for (int i = 0; i < pos.row; i++) {
        if (queens[i].col == pos.col || queens[i].row + i == pos.row + pos.col
            || queens[i].row - i == pos.row - pos.col) {
            return false;
        }
    }
    return true;
}

// 递归求解 n 皇后问题
void solveNQueens(int n, vector<QueenPos>& queens, stack<QueenPos>& s) {
    if (n == 0) {
        cout << "一种解法：";
        for (int i = 0; i < n; i++) {
            cout << " " << queens[i].row << " " << queens[i].col;
        }
        cout << endl;
        return;
    }

    for (int i = 0; i < n; i++) {
        QueenPos pos = {i, 0};
        if (isSafe(pos, queens)) {
            queens.push_back(pos);
            solveNQueens(n - 1, queens, s);
            queens.pop_back();
        }
    }
}

int main() {
    int n;
    cout << "请输入皇后数量 n (n <= 20): ";
    cin >> n;

    vector<QueenPos> queens;
    stack<QueenPos> s;
    solveNQueens(n, queens, s);

    cout << "所有解法：" << endl;
    while (!s.empty()) {
        cout << "一种解法：";
        QueenPos pos = s.top();
        s.pop();
        for (int i = 0; i < n; i++) {
            cout << " " << pos[i].row << " " << pos[i].col;
            pos[i].col++;
        }
        cout << endl;
    }

    return 0;
}
